package main

import "fmt"
/**
1.建堆
2.堆排序
 */

//堆排序
func heapSort(tree []int) {
	buildHeap(tree)
	fmt.Println(tree)
	n := len(tree)
	for i := n - 1; i >= 0; i-- {
		swap(tree, i, 0)
		heapify(tree, i, 0)
	}
}

//建堆 (大根堆)
func buildHeap(tree []int) {
	n := len(tree)
	p := (n - 2) / 2
	for i := p; i >= 0; i-- {
		heapify(tree, n, i)
	}
}

/**
n 总节点数
heapify作用的节点
*/
func heapify(tree []int, n int, i int) {
	max := i
	c1 := 2*i + 1
	c2 := 2*i + 2
	if c1 < n && tree[c1] > tree[max] { //注意这里用的是max
		max = c1
	}

	if c2 < n && tree[c2] > tree[max] {
		max = c2
	}

	if max != i {
		swap(tree, max, i)
		heapify(tree, n, max)
	}
}

func swap(tree []int, a int, b int) {
	tree[a], tree[b] = tree[b], tree[a]
}
